import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 手动实现哈夫曼树（赫夫曼树，最优二叉树）：根据一个无序数组，并将其构建成一个哈夫曼树
 */
public class HuffmanTree {
    public static void main(String[] args) {
        int[] ints = {13, 7, 8, 3, 29, 6, 1};
        Node huffmanTree = createHuffmanTree(ints);
        System.out.println("哈夫曼树根节点："+huffmanTree);
        System.out.println("前序输出哈夫曼树：如下所示");
        //前序遍历输出
        preOrder(huffmanTree);
    }

    //构建哈夫曼树方法
    public static Node createHuffmanTree(int[] arr){
        //1.将数组的的一个个数据转化为一个个最简二叉树,并放入一个集合中，即将数据分别赋给二叉树节点的权值
        List<Node> nodeList = new ArrayList<>();//创建一个list集合，用于收纳一个个最简二叉树
        for (int i : arr) {
            Node node = new Node(i);
            nodeList.add(node);
        }

        while (nodeList.size() > 1) {//只剩最后一个元素的时候，那个元素就是哈夫曼树的根节点

            //2.将集合中元素进行排序，后面构建新二叉树都要排序
            Collections.sort(nodeList);//自然排序

            //3.依次取出集合中最前面的两个最简二叉树，构建一棵新的二叉树，新的二叉树根节点权值就是前两个二叉树根节点权值的和，
            //再将新二叉树的根节点权值放到剩下的集合中去排序，再重复2，3步骤，直到所有元素都被处理过为止
            Node nodeLeft = nodeList.get(0);//取出第一个元素
            Node nodeRight = nodeList.get(1);//取出第二个元素
            //构建新二叉树
            Node newBinaryTree = new Node(nodeLeft.value + nodeRight.value);
            newBinaryTree.left = nodeLeft;
            newBinaryTree.right = nodeRight;
            //删除已经处理过的元素
            nodeList.remove(nodeLeft);
            nodeList.remove(nodeRight);
            //将新二叉树添加到集合中去
            nodeList.add(newBinaryTree);

        }
        return nodeList.get(0);
    }

    //二叉树的前序遍历方法
    public static void preOrder(Node node){
        if (node == null) {
            System.out.println("二叉树为空，没有可以遍历的数据！");
            return;
        }
        System.out.println(node);
        if (node.left != null) {
            preOrder(node.left);
        }
        if (node.right != null) {
            preOrder(node.right);
        }

    }
}

//创建哈夫曼树的节点元素
class Node implements Comparable<Node>{//实现Java比较器接口，方便数组排序使用
    int value;//节点的权值
    Node left;//左节点
    Node right;//右节点

    public Node(int value) {
        this.value = value;
    }

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }

    //实现自然排序方法：自然排序就是从小到大排序
    @Override
    public int compareTo(Node o) {
        //判断两个对象大小的依据，若this对象 > o对象，则返回正整数
        //注意：从小到大排序，就必须是this对象 - o对象值
        return this.value - o.value;
    }

}